uva 514

ACM
评论

《算法入门》P140
关于uva这个判题啊，我的内心是崩溃的，PE就判WA。

我的想法：把出栈次序看成入栈次序，那么出栈就是固定的1-n,反向入栈，每个元素先入栈，再判断栈顶元素是否是应该出栈的元素。如果最后栈里还有元素，那么就是不合法序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include<vector>
#include<iostream>
#include<stdio.h>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<stack>
#include<numeric>
#include<algorithm>
#include<set>
using namespace std;
#pragma comment(linker, "/STACK:10240000000,10240000000")
#define mem(x,y) memset(x,y,sizeof(x))
#define mec(x,y) memcpy(x,y,sizeof(x))
#define debug puts("============")
#define eps 1e-5
#define mp(x,y) make_pair(x,y)
#define inf 0x3f3f3f3f
#define NV 150
#define nit int
#define mian main
#define ture true
#define ll long long
#define maxn 100+4
#define sf(x) scanf("%d",&x)
#define sff(x,y) scanf("%d%d",&x,&y)
#define sfff(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define NE 3000
int n;
int out[1010];
int main()
{
    while(sf(n),n)
    {
        while(sf(out[1]),out[1])
        {
        stack<int>s;
        int j=n;
        for(int i=2;i<=n;i++)sf(out[i]);
        int i=n+1;
        while(i--)
        {
            s.push(out[i]);
            while(!s.empty()&&s.top()==j)s.pop(),j--;
        }
        if(s.empty())puts("Yes");
        else puts("No");
        }
        puts("");
    }
}

我的另一种想法，正向入栈。如果栈是空的，或者栈顶元素不是当前应出栈元素，那么就一直进栈，知道遇到应出栈元素或入栈截止。遇到应出栈元素后，跳过该元素的入栈，进入下一循环。仍然是判断栈是否为空来确定序列的合法性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int n;
int out[1010];
int main()
{
    while(sf(n),n)
    {
        int t;
        while(sf(t),t)
        {
        stack<int>s;
        int j=1;
        out[0]=t;
        for(int i=1;i<n;i++)sf(out[i]);
        for(int i=0;i<n;i++)
        {
            if(s.empty()||s.top()!=out[i])
            {
                while(j!=out[i]&&j<n)s.push(j++);
                j++;
            }
            else if(s.top()==out[i])s.pop();
        }
        if(s.empty())puts("Yes");
        else puts("No");
        }
        puts("");
    }
}

Srbga用的是我的第二种方法，判断非法的原则是出栈截止之前还能否进行合法操作，合法操作有三：当前进栈等于当前出栈，进栈++，出栈++；栈顶等于当前出栈，pop；非前两者，下一元素入栈。
因为其方法没我的优越，就不上代码了。

这种题，一般样例能过就能A。- -。不得不说，报个PE会死爹啊，我这两天每道uva的题都因为空行WA了。

EOF